package com.roy.wakeupes.utils;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class BidirectionalMaximumMatching {

    public static void main(String[] args) {
        String text = "自然语言处理是人工智能和语言学领域的分支学科";
        List<String> dictionary = new ArrayList<>();
        // 假设词典已经加载
        dictionary.add("自然");
        dictionary.add("语言");
        dictionary.add("处理");
        dictionary.add("是");
        dictionary.add("人工智能");
        dictionary.add("和");
        dictionary.add("语言学");
        dictionary.add("领域");
        dictionary.add("分支");
        dictionary.add("学科");

        List<String> fmmResult = forwardMaximumMatching(text, dictionary);
        List<String> bmmResult = backwardMaximumMatching(text, dictionary);
        // 取交集作为最终结果
        Set<String> commonElements = new HashSet<>(fmmResult);
        commonElements.retainAll(new HashSet<>(bmmResult));
        List<String> finalResult = new ArrayList<>(commonElements);

        // 打印分词结果
        System.out.println(finalResult);
    }

    public static List<String> forwardMaximumMatching(String text, List<String> dictionary) {
        List<String> tokens = new ArrayList<>();
        int start = 0;
        while (start < text.length()) {
            int maxEnd = start;
            for (int end = start + 1; end <= text.length(); end++) {
                String word = text.substring(start, end);
                if (dictionary.contains(word) && end == start + word.length()) {
                    maxEnd = end;
                }
            }
            tokens.add(text.substring(start, maxEnd));
            start = maxEnd;
        }
        return tokens;
    }

    public static List<String> backwardMaximumMatching(String text, List<String> dictionary) {
        List<String> tokens = new ArrayList<>();
        int end = text.length();
        while (end > 0) {
            int maxStart = end;
            for (int start = end - 1; start >= 0; start--) {
                String word = text.substring(start, end);
                if (dictionary.contains(word) && start == end - word.length()) {
                    maxStart = start;
                }
            }
            tokens.add(text.substring(maxStart, end));
            end = maxStart;
        }
        return tokens;
    }
}